Back to course home
0% completed
Vote For New Content
Microsoft Hard Problems
Regular Expression Matching (hard)
Solution: Regular Expression Matching
First Missing Positive (hard)
Solution: First Missing Positive
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Sliding Window Maximum (hard)
Solution: Sliding Window Maximum
Count Unique Characters of All Substrings of a Given String (hard)
Solution: Count Unique Characters of All Substrings of a Given String
Word Ladder (hard)
Solution: Word Ladder
Word Ladder II (hard)
Solution: Word Ladder II
Number of Flowers in Full Bloom (hard)
Solution: Number of Flowers in Full Bloom
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Longest Arithmetic Subsequence (medium)
Problem Statement
Given an array nums containing positive integers, return the maximum length of a subsequence that forms an arithmetic progression.
-
A
subsequenceis an array that can be formed fromnumsby deleting 0 or more elements without changing the order of the remaining elements. -
An arithmetic progression (AP) is a sequence of numbers in which the difference between any two consecutive elements is constant. In short,
seq[i + 1] - seq[i]should be same for all0 <= i < seq.length - 2.
Examples
-
Example 1:
- Input:
[8, 12, 6, 4, 2] - Expected Output:
4 - Justification: The subsequence
[8, 6, 4, 2]forms the longest arithmetic subsequence with a common difference of -2, thus the longest arithmetic subsequence has a length 4.
- Input:
-
Example 2:
- Input:
[5, 10, 15, 7, 11, 5] - ****Expected Output:
3 - Justification:** The subsequence [5, 10, 15] forms the longest arithmetic subsequence with a common difference of 5.
- Input:
-
Example 3:
- Input:
[1, 7, 10, 15, 27, 29] - Expected Output:
3 - Justification: The subsequence [1, 15, 29] forms the longest arithmetic subsequence with a common difference of 14.
- Input:
Try it yourself
Try solving this question here:
Java
Saved to Cloud
. . . .
Solution: Reverse Words in a String II
Solution: Longest Arithmetic Subsequence
Mark as Completed
On this page
Problem Statement
Examples
Try it yourself